1. Field of the Invention
The present invention relates to the improvement in image quality by the prevention of aliasing, and more particularly, the improvement of image quality by hierarchial pattern matching with variable-sized templates.
2. Description of the Related Art
In the output of printing systems, diagonal lines and edges may appear coarse or jagged, exhibiting a stair- step appearance ("jaggies") as illustrated in FIG. 1. This appearance is the result of spurious high-frequency components (aliasing) from an image, the high-frequency components typically originating in bitmap representations and raster output devices such as CRT displays and laser printers due to unavoidable transitions introduced into a continuous image during quantization.
Two common methods of reducing the effect of jaggies are to: 1) increase the spatial resolution; and 2) perform anti-aliasing. If the steps between adjacent picture elements (pixels) are sufficiently small, the eye will integrate the steps into a smooth curve. The increased spatial resolution, however, requires additional memory capability and more complex and expensive output devices.
Anti-aliasing thus provides an alternative to increased spatial resolution. In traditional signal processing, anti-aliasing is accomplished in the frequency domain through the application of a low-pass filter. Spatial domain image processing, however, is advantageous over frequency domain processing since spatial domain processing tends to be less computationally intensive and more intuitive.
A standard approach to spatial anti-aliasing is to use a computer to simulate a flying spot scanner. A spot of fixed size scans the image in raster fashion. The source image (typically a bitmap) is effectively sampled at a lower rate, with each pixel in the output being the average value of the area illuminated by the spot at a given time. The spot is simulated by a rectangular region or filter containing a set of possibly weighted values. FIG. 2 illustrates such a filter.
The filter such as the filter of FIG. 2 is then overlaid on the image and applied to the entire image in chunks the size of the filter. At each stop, the value of the output pixel is the average of the image pixels lying beneath the filter.
If the weights in the filter are non-uniform, each pixel is multiplied by the corresponding weight prior to the averaging of the image pixels.
Changing the weights will simulate different spot sizes. The larger the filter and the more uniform the weights, the broader the anti-aliasing action will be. The visual effect is that the image will appear slightly blurred. Taken to the extreme, one could imagine a filter the size of the entire image. The output would be a single pixel whose value is the overall average intensity of the original image.
The spatial filter has the advantage of being easy to implement and easy to characterize, since all of the signal-processing literature on low-pass filtering is applicable thereto. However, the spatial filtering has a significant disadvantage when applied to the domain of font processing. In this application, the very uniformity and lack of discrimination of the filter becomes a significant problem. Letter forms consist of vertical, horizontal and angled strokes and, in most fonts, smooth curves. Since raster devices (CRT's and printers) can display both vertical and horizontal strokes without any aliasing, it is undesirable to apply anti-aliasing to such strokes, since the application of anti-aliasing degrades the sharpness of the edges and can change the apparent edge location of a stroke. Unfortunately, the spatial filter has no way of knowing what sort of edge it is filtering. The standard solution to this problem is to filter the character in a different phase, with the starting location of the filter slightly offset, so that the edge of the stroke to be left alone falls just between successive applications of the filter. While this method is an improvement over plain filtering, it cannot guarantee that all vertical and horizontal strokes will be skipped. For example, if a phase is selected to skip the first vertical stroke in the character "H", it may hit the second vertical stroke, if the distance between the two strokes is not an even multiple of the width of the filter. In addition, the amount of processing required for each character is increased.
An alternative to spatial filtering by integration is geometric filtering. In geometric filtering, the image is scanned with a rectangular region. The content of the region at any given time is treated as the left-hand side of a potentially arbitrary replacement rule. Thus, for any given pattern being considered, a user may specify exactly what pixel, or combination of pixels, should be placed in an output image to achieve a desired effect.
Geometric filtering can be applied to anti-aliasing for bitmap characters. For example, one level of gray can be added to binary (black and white) characters. Thus, the input is a binary bitmap, and the output is a bitmap stored using two bits per pixel, where each pixel can be either black, white or gray. Gray pixels are added to "fill in" steps along diagonal edges. FIG. 3 illustrates a 2.times.2 square template which can be passed over the image of the character.
At any given location, the template can contain one of 16 (2.sup.4) different pixel arrangements. A determination is made of what the output image should look like at the point of each of the 16 pixel arrangements. If all four pixels are white, it is determined that no further processing is needed since the character has not been reached. Therefore, the output is also four white pixels. Likewise, the case of four black pixels is identical by symmetry. If two pixels in the right hand column are black and the two pixels in the left hand column are white, it is determined that the left-hand edge of a vertical stroke is entered. Thus, no anti-aliasing need be applied. These pixels are illustrated in FIG. 4. Likewise, the case of two black pixels in a horizontal row is identical by symmetry.
The only unique template needed identifies areas that should have gray added, i.e., three black pixels and one white pixel. As illustrated in FIGS. 5a-5d, there are four similar templates by square symmetry. If this case is encountered, the black pixels are copied to the output, and the white pixel is replaced by a gray pixel. Thus, it is ensured that gray pixels are only added along diagonal edges.
In pattern matching, the size of the template used determines the complexity of processing operations which could be performed. For example, the 2.times.2 template can be used to add gray pixels to 45.degree. stair steps and bitmap images. Likewise, 3.times.3 templates can also be used to add gray pixels, but can selectively place two different levels of gray, while identifying regions of half bits in characters and replacing these regions with gray. The problem with pattern-matching is that if the size of the template is increased, the amount of memory needed to store the associated look-up table for specifying the replacement patterns increases exponentially. For example, a 2.times.2 table contains 16 entries, while a 3.times.3 table contains 512 entries. The future trend for printers appears to be in a direction of providing more levels of gray, up to 16 bits per pixel. To allocate these bits meaningfully in the context of pattern matching would require a 16.times.16 template.
Other methods have been disclosed for improving image quality in printing systems by reducing aliasing.
In U.S. Pat. No. 4,780,711 to Doumas, an assumed boundary lines method is described. In this method, an array of pixels in an image is selected and compared to a plurality of predetermined pixel array patterns. When a match is found, an assumed contour line is determined running through the array. The intensity of the center pixel of the array is chosen based on the angle of the assumed line through the array.
In the U.S. Pat. No. 4,517,604 to Lasher et al., print element (pel or pixel) data is scanned into two arrays. The first array is scanned row by row to identify any black or white pel runs. White or black pels in the second array are overwritten with gray pels as a function of the pel runs identified in the first array. The method is then repeated column by column. The resulting second array will have reduced line width variations when compared to the first array.
U.S. Pat. No. 4,437,122 to Walsh et al. utilizes shift registers with decoders to generate an appropriate signal. Successive lines of pixel data are stored in successive parallel shift registers that are coupled to decoders. In these decoders, pixels surrounding a specific pixel are compared to each other in order to generate print head driving signals depending on whether curved or straight lines are being formed.
Another approach in controlling quality is shown in U.S. Pat. No. 4,486,785 to Lasher et al., where gray scale pels are introduced in close proximity to unit steps in a bitmap image. Whenever a unit step is found, the distance between the step and the nearest transition is computed. This distance is used in a look- up table for the appropriate gray scale values.
In U.S. Pat. No. 4,646,355 to Petrick et al., a method is shown for the removal of unwanted dots and voids. In this method, the user defines the smallest data item of a bitmap. Images smaller than this data item are removed in accordance with comparisons performed in a pixel window. In an n.times.n window of pixels, pixels along the perimeter are examined. If bordering pixels are of the same intensity, the internal pixels are changed to match these bordering pixels.
In U.S. Pat. No. 4,681,424 to Kantor et al., a method is disclosed for increasing the width of single pixel lines by advancing the leading edge of pulses defining a white-to-black transition and delaying the trailing edge of pulses defining a black-to-white transition. For lines parallel to the scan direction, gray pulses are added to widen lines. In U.S. Pat. No. 4,847,641 to Tung, a method is disclosed for image enhancement through template matching. Piecewise bitmap patterns are matched to replace the central bit in the pattern with a unique compensation bit.
The use of pattern matching is an important technique for image processing, but, as discussed above, requires a large memory capacity to store the associated look-up table for specifying replacement patterns. Thus, the implementation of a pattern matching technique using templates much larger than would be possible under the standard table look-up is desired.